/*
 * Atomic Predicates for Transformers
 * 
 * Copyright (c) 2015 UNIVERSITY OF TEXAS AUSTIN. All rights reserved. Developed
 * by: HONGKUN YANG and SIMON S. LAM http://www.cs.utexas.edu/users/lam/NRL/
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * with the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * 1. Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimers.
 * 
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimers in the documentation
 * and/or other materials provided with the distribution.
 * 
 * 3. Neither the name of the UNIVERSITY OF TEXAS AUSTIN nor the names of the
 * developers may be used to endorse or promote products derived from this
 * Software without specific prior written permission.
 * 
 * 4. Any report or paper describing results derived from using any part of this
 * Software must cite the following publication of the developers: Hongkun Yang
 * and Simon S. Lam, Scalable Verification of Networks With Packet Transformers
 * Using Atomic Predicates, IEEE/ACM Transactions on Networking, October 2017,
 * Volume 25, No. 5, pages 2900-2915 (first published as IEEE Early Access
 * Article, July 2017, Digital Object Identifier: 10.1109/TNET.2017.2720172).
 * 
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH
 * THE SOFTWARE.
 */
package transformer;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

import common.BDDACLWrapper;
import common.ForwardingRule;

public class DynamicForwardingTable {

    BDDACLWrapper bddengine;
    PrefixTreeNode root;
    HashMap<String, Integer> fwbdds;



    public DynamicForwardingTable()
    {
        root = new PrefixTreeNode();
        fwbdds = new HashMap<String, Integer> ();

        bddengine = new BDDACLWrapper();
        PrefixTreeNode.bddengine = bddengine;
    }

    public boolean applyChanges(int delta, String addport, PrefixTreeNode parent)
    {
        if(delta == BDDACLWrapper.BDDFalse)
        {
            return false;
        }

        if(parent == null)
        {
            applyChangesAdd(delta, addport);
        }else{
            if(parent == root && parent.isInvalid())
            {
                applyChangesAdd(delta, addport);
            }else
            {
                return applyChanges(delta, addport, parent.getEffectivePort());
            }
        }

        return true;
    }

    public boolean applyChanges(int delta, PrefixTreeNode parent, String delport)
    {
        if(delta == BDDACLWrapper.BDDFalse)
        {
            return false;
        }


        if(parent == root && parent.isInvalid())
        {
            applyChangesDel(delta, delport);
        }else
        {
            return applyChanges(delta, parent.getEffectivePort(), delport);
        }

        return true;
    }

    /**
     * 
     * @return true - port predicates are changed
     *               false- port predicates are not changed
     */
    public boolean applyChanges(int delta, String addport, String delport)
    {
        if(addport.equals(delport))
        {
            return false;
        }

        applyChangesAdd(delta, addport);

        applyChangesDel(delta, delport);

        return true;
    }

    public void applyChangesAdd(int delta, String addport)
    {

        int addBdd = BDDACLWrapper.BDDFalse;
        if(fwbdds.containsKey(addport))
        {
            addBdd = fwbdds.get(addport);
        }
        addBdd = bddengine.orTo(addBdd, delta);
        fwbdds.put(addport, addBdd);

    }

    public void applyChangesDel(int delta, String delport)
    {
        int delBdd = fwbdds.get(delport);
        delBdd = bddengine.diffTo(delBdd, delta);
        fwbdds.put(delport, delBdd);
    }

    public DynamicForwardingTable(List<ForwardingRule> rules)
    {
        this();
        addRules(rules);

    }

    /**
     * 
     * @param rule
     * @return true - port predicates are changed
     *               false -  not changed
     */
    public boolean addRule(ForwardingRule rule)
    {
        PrefixTreeNode node = null;
        if(rule.isDefault())
        {
            root.addPort(rule.getiname());
            node = root;

            // update fwbdds
            if(node.getEffectivePort().equals(rule.getiname()))
            {
                return applyChanges(node.effectivebdd, node.getEffectivePort(), node.parent);
            }

        }else
        {
            node = root.insert_to_tree(rule);

            // update fwbdds
            if(node.getEffectivePort().equals(rule.getiname()))
            {
                return applyChanges(node.effectivebdd, rule.getiname(), node.parent);
            }
        }

        return false;


    }



    /**
     * return number of port predicates changes
     * @param rules
     */
    public int addRules(List<ForwardingRule> rules)
    {
        int predicate_changes = 0;
        for(ForwardingRule one_rule : rules)
        {
            if(addRule(one_rule))
            {
                predicate_changes ++;
            }
        }
        return predicate_changes;
    }

    /**
     * true - predicate changes
     * false - not change
     * @param rule
     */
    public boolean deleteRule(ForwardingRule rule)
    {
        if(rule.isDefault())
        {
            if(!root.isInvalid())
            {
                if(rule.getiname().equals(root.getEffectivePort()))
                {
                    root.removePort(rule.getiname());
                    // update fwbdds
                    if(root.isInvalid())
                    {
                        applyChangesDel(root.effectivebdd, rule.getiname());
                        return true;
                    }else
                    {
                        return applyChanges(root.effectivebdd, root.getEffectivePort(), rule.getiname());
                    }
                }else{
                    root.removePort(rule.getiname());
                }
            }
        }else
        {
            PrefixTreeNode node = root.search(rule);
            if(node != null)
            {
                if(rule.getiname().equals(node.getEffectivePort()))
                {
                    node.removePort(rule.getiname());

                    if(node.isInvalid())
                    {
                        PrefixTreeNode parent = node.delete_from_tree();
                        parent.effectivebdd = bddengine.orTo(parent.effectivebdd, node.effectivebdd);

                        // update fwbdds
                        boolean res = applyChanges(node.effectivebdd, parent, rule.getiname());
                        
                        bddengine.deref(node.effectivebdd);
                        bddengine.deref(node.prefixbdd);
                        
                        return res;
                        
                    }else
                    {
                        // update fwbdds
                        return applyChanges(node.effectivebdd, node.getEffectivePort(), rule.getiname());
                    }

                }else
                {
                    node.removePort(rule.getiname());
                }
            }
        }

        return false;
    }

    /**
     * 
     */
    public int deleteRules(List<ForwardingRule> rules)
    {
        int predicate_changes = 0;
        for(ForwardingRule one_rule : rules)
        {
            if(deleteRule(one_rule))
            {
                predicate_changes ++;
            }
        }
        
        return predicate_changes;

    }

    public static double[] test_one_router(String dname) throws IOException
    {
        Device d = BuildNetwork.parseDevice(dname, "i2old/"+dname+"ap");
        ArrayList<ForwardingRule> alllist = d.fws;
        int break_point = (int) (d.fws.size()*0.9);
        ArrayList<ForwardingRule> list1 = 
                new ArrayList<ForwardingRule> (alllist.subList(0, break_point));
        ArrayList<ForwardingRule> list2 = 
                new ArrayList<ForwardingRule>(alllist.subList(break_point, d.fws.size()));

        DynamicForwardingTable dft = new DynamicForwardingTable(list1);

        double[] times = new double[5];

        long t1 = System.currentTimeMillis();
        times[3] = dft.addRules(list2);
        long t2 = System.currentTimeMillis();

        Collections.reverse(list2);
        long t3 = System.currentTimeMillis();
        times[4] = dft.deleteRules(list2);
        long t4 = System.currentTimeMillis();

        System.out.println("total number of rules: " + alllist.size());

        System.out.println("add rules time: "+(t2-t1)+" ms");
        System.out.println("num of predicate changes: " + times[3]);
        System.out.println("del rules time: " + (t3-t2)+" ms");
        System.out.println("num of predicate changes: " + times[4]);
        int num_changes = list2.size();
        System.out.println("number of rules changed: " + num_changes);
        System.out.println("----------------------------------------");

        times[0] = t2-t1;
        times[1] = t4-t3;
        times[2] = num_changes;

        return times;
    }

    public static void testI2() throws IOException
    {
        String [] devicenames = {"atla","chic","hous","kans","losa","newy32aoa","salt","seat","wash"};
        double [] results = new double[5];

        for(String dname : devicenames)
        {
            double[] res = test_one_router(dname);
            for(int i = 0; i < res.length; i ++)
            {
                results[i] += res[i];
            }
        }
        
        System.out.println("total number of rule updates: " + results[2]);
        System.out.println("average time for adding rule: " + (results[0]/results[2]));
        System.out.println("percentage of predicate change for adding rule: " + (results[3]/results[2]));
        System.out.println("average time for deleting rule: " + (results[1]/results[2]));
        System.out.println("percentage of predicate change for deleting rule: " + (results[4]/results[2]));
        
    }

    public static void main(String [] args) throws IOException
    {

        testI2();
        
        



    }

    /**
     *         ArrayList<ForwardingRule> fws = new ArrayList<ForwardingRule> ();
        fws.add(new ForwardingRule(0,0,"1"));
        fws.add(new ForwardingRule(0,30,"2"));
        fws.add(new ForwardingRule(8,30,"2"));
        fws.add(new ForwardingRule(12,30,"3"));
        fws.add(new ForwardingRule(2,31,"3"));
        fws.add(new ForwardingRule(8,30,"3"));
        fws.add(new ForwardingRule(0,0,"3"));

        DynamicForwardingTable dft = new DynamicForwardingTable();

        for(int i = 0; i < fws.size(); i ++)
        {
            dft.addRule(fws.get(i));
            System.out.println(dft.fwbdds);
            System.out.println("+++++++++++++++");
            System.out.println(dft.bddengine.getfwdbdds(new ArrayList<ForwardingRule>(fws.subList(0, i+1))));
            System.out.println("-------------------------------------");
        }
        
               DynamicForwardingTable dft = new DynamicForwardingTable(fws);

        
        for(int i = fws.size()-1; i >= 0; i --)
        {
            dft.deleteRule(fws.get(i));
            System.out.println(dft.fwbdds);
            System.out.println("+++++++++++++++");
            fws.remove(i);
            System.out.println(dft.bddengine.getfwdbdds(fws));
            System.out.println("-------------------------------------");
        }
        
        dft.deleteRule(fws.get(1));
        System.out.println(dft.fwbdds);
        System.out.println("+++++++++++++++");
        fws.remove(1);
        System.out.println(dft.bddengine.getfwdbdds(fws));
        System.out.println("-------------------------------------");
        

     */

}
